The present invention relates generally to rasterizers and, more particularly, to the conversion of primitives defined by vertexes to equivalent images composed of pixel patterns without clipping the primitives.
In a traditional computer graphics pipeline, drawn primitives such as lines or polygons sometimes extend from on-screen to off-screen, and a xe2x80x9cclip stagexe2x80x9d in the pipeline alters the shape of the primitives to clip them to include only the on-screen portion. The rasterizer stage then generates the pixels corresponding to the on-screen portion of the primitive. This xe2x80x9cclip stage,xe2x80x9d however, often reduces the performance of the graphics pipeline because the computations involved are complex and highly variable.
There are several ways in which vertex coordinates of a primitive may extend beyond the portion that should be drawn. The most obvious way is extending beyond the top, bottom, left, and/or right edges of the screen, or window. FIG. 1 shows a triangle 100 clipped by the screen edges thus rendering a seven-sided polygon 102. It should be noted that in some prior art systems, a xe2x80x9cguard bandxe2x80x9d is defined about an outer perimeter of the screen. By employing the guard band as the xe2x80x9ccut-off,xe2x80x9d some primitives that extend beyond the screen, but not beyond the guard band may avoid clipping. By employing a guard band, clipping is thus reduced, but not completely avoided.
Yet another type of clipping involves the third xe2x80x9cZxe2x80x9d dimension or, in other words, the dimension extending xe2x80x9cintoxe2x80x9d or xe2x80x9cout ofxe2x80x9d the screen. Most graphics systems clip primitives against xe2x80x9cnearxe2x80x9d and xe2x80x9cfarxe2x80x9d limits, or planes. This is primarily done to control the range of the Z coordinate, so it can be expressed with adequate precision. This, however, also can add two more imposed edges on a polygon.
Another consequence of not clipping is more obscure. Before drawing a 3-D triangle, it is projected on to a 2-D image plane. Commonly, the mathematical projection involves perspective, making nearby objects appear large and far objects appear smaller. In a 3-D Cartesian coordinate system with X, Y, and Z axes that has the viewer looking down the +Z axis, this perspective is often accomplished by dividing the 3-D X and Y coordinates by the Z coordinate. Thus objects twice as far away, or twice the distance along the Z axis, have only half the screen-space X and Y extent.
A problem arises when an object spans both the +Z and xe2x88x92Z half-spaces. Division by a negative Z can produce reasonable on-screen X and Y values. As a result, points with a negative Z may project upside down and backwards on to the screen similar to positive Z points. An example of this phenomenon is shown in FIG. 1A. As shown, an end 110 of a long triangle 112 is in front of the hypothetical xe2x80x9ccameraxe2x80x9d or viewpoint 114, with +Z coordinates, while the another end 116 is behind the camera with a xe2x88x92Z coordinate. FIG. 1B shows that after projection, all three vertexes 118, 120 and 122 are on-screen when only two of them (118 and 120) are legitimate and the other one (122) is a projection from behind the camera.
Ordinarily, conventional clipping procedures would have eliminated the part of the triangle behind the camera, cutting off the xe2x88x92Z portion at the bottom of the screen. One example of avoiding the foregoing conventional clipping procedures may be found with reference to xe2x80x9cTriangle Scan Conversion using 2D Homogeneous Coordinatesxe2x80x9d authored by Marc Olano and Trey Greer, published in the 1997 Siggraph/Eurographics Workshop, and which is incorporated herein by reference in its entirety. Such technique, however, fails to deliver a sizable increase in performance.
There is therefore a need for a rasterization system that can handle primitives with any post-transform vertex coordinates that extend beyond the edges of the screen for the purpose of avoiding standard clipping operations while increasing processing performance.
A method, apparatus and article of manufacture are provided for clip-less rasterization. First, a primitive, i.e. line, triangle, etc., is received that is defined by a plurality of vertices. Each of such vertices includes a W-value. Thereafter, an area is identified based on the W-values of the vertices. Such area is representative of a portion of a display to be drawn corresponding to the primitive. As will become apparent, the area enclosed by the primitive is not always the area to be rasterized.
The instant process employs a variable, W, that is commonly used for projection, i.e., for viewing objects in perspective. The variable W is a number that the other coordinates, X, Y and Z, are divided by in order to make nearby things larger and far things smaller. The variable W is representative of a distance between a xe2x80x9ccenter of projectionxe2x80x9d and the corresponding vertex.
In one embodiment where the primitive is a triangle, if none of the vertices have a negative W-value, the sides of the triangle enclose the area. On the other hand, if only one of the vertices has a negative W-value, the area is positioned outside an edge of the primitive opposite the vertex having the negative W-value. In particular, the area to be drawn is bounded by two lines that are co-linear with the two triangle sides sharing the xe2x88x92W vertex, and further bounded by a side of the triangle that shares the two +W vertexes. Still yet, if only two of the vertices have negative W-values, the area is positioned outside the primitive opposite both of the vertices having the negative W-values. In other words, the area to be drawn is bounded by two lines that are co-linear with the two triangle sides sharing the +W vertex, and further contiguous to the +W vertex.
The present invention is thus capable of handling all three of the foregoing cases. If the vertices are off-screen, it draws only the on-screen portion. If part of the triangle is beyond the near and/or far plane, it draws only the portion within those planes. If the triangle has one or two negative Z vertexes, only the correct +Z portion is drawn. By limiting the traversal using line equations and Z testing, little time is wasted exploring xe2x80x9cbadxe2x80x9d pixels that fail an edge or Z test. This is possible because all clipping, by screen edge or near or far plane, results in a convex region on-screen which can be xe2x80x9cexploredxe2x80x9d easily because of its convex nature.
In one aspect of the present invention, positioning a plurality of points on or near the area, and moving the points about in the area identifies the space in the area. The points may define an enclosed polygonal region. As an option, the points may be initially positioned on top of the display if a top vertex of the area is positioned outside boundaries of the display.
These and other advantages of the present invention will become apparent upon reading the following detailed description and studying the various figures of the drawings.